/**
 * https://leetcode-cn.com/problems/longest-palindromic-subsequence/
 * 最长回文子序列
 * @param s 
 */
const longestPalindromeSubseq = (s: string): number => {
    const len = s.length;
    // 全部填充0
    const dp: number[] = new Array(len).fill(0)

    // 从后往前遍历, 因为前面的可能需要用到后面结果
    for (let i = len - 1; i >= 0; i--) {
        // 范围i~i肯定是1

        // 先保存起来, cur默认是第一项
        let cur = 0

        // 将第一项赋值为1
        dp[i] = 1
        // 处理当前行的下标i的后面部分
        for (let j = i + 1; j < len; j++) {
            let leftBottom = cur;
            //!特别注意下标要取j
            // 保存当前的项, 下一次作为leftBottom
            cur = dp[j]
            if (s[j] === s[i]) {
                // 相等, 取左下角 + 2
                dp[j] = leftBottom + 2
            } else {
                // 不相等, 取分别去除左右一个的最大值
                dp[j] = Math.max(dp[j - 1], dp[j])
            }
        }
    }
    return dp[len - 1]
};


const longestPalindromeSubseq2 = (s: string): number => {
    // bbbab

    // dp[i, j] 表示下标范围i~j的最长回文子序列长度

    // 状态转移方程
    // 不相等: dp[i, j] =  max{往左边, 往下标}
    // 相等, 找它的左下角: dp[i, j] = 左下角 + 2

    const len = s.length;
    // 全部填充0
    const dp: number[][] = new Array(len).fill(0).map(_ => new Array(len).fill(_))

    // 从后往前遍历, 因为前面的可能需要用到后面结果
    for (let i = len - 1; i >= 0; i--) {
        // 范围i~i肯定是1
        dp[i][i] = 1

        // 处理当前行的下标i的后面部分
        for (let j = i + 1; j < len; j++) {
            if (s[j] === s[i]) {
                // 相等, 取左下角 + 2
                dp[i][j] = dp[i + 1][j - 1] + 2
            } else {
                // 不相等, 取分别去除左右一个的最大值
                dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j])
            }
        }
    }
    return dp[0][len - 1]
};

longestPalindromeSubseq('bbbab')